'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-14 21:37:41
'''
#
# @lc app=leetcode.cn id=1122 lang=python3
#
# [1122] 数组的相对排序
#

# @lc code=start
from typing import List
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        import collections
        store = collections.defaultdict(lambda:0)
        for i in arr1:
            store[i]+=1
        ans = []
        re = []
        for i in arr2:
            if i in store:
                while store[i]:
                    re.append(i)
                    store[i]-=1
        for k, v in store.items():
            while v:
                ans.append(k)
                v-=1
        ans.sort()
        re.extend(ans)
        return re

# @lc code=end

